本章的讲解围绕向量结构的高效实现而逐步展开，包括其作为抽象数据类型的接口规范以及对应的算法，尤其是高效维护动态向量的技巧。此外，还针对有序向量，系统介绍经典的查找与排序算法，并就其性能做一分析对比，这也是本章的难点与重点所在。最后，还引入复杂度下界的概念，并通过建立比较树模型，针对基于比较式算法给出复杂度下界的统一界定方法。
- 数据结构是数据项的结构化集合。数据结构划分为线性结构、半线性结构和非线性结构三大类。
- 最为基本的线性结构统称为序列(sequence)，根据其中数据项的逻辑次序与其物理存储地址的对应关系不同，又可进一步地将序列分为向量(Vector)和列表(List)。
- 在向量中，所有数据项的物理存放位置与其逻辑次序完全吻合，此时的逻辑次序也称作秩(Rank)。而在列表中，逻辑上相邻的数据项在物理上未必相邻，而是采用间接定址的方式通过封装后的位置(position)相互引用。
从数组到向量
数组
- 具体地，数组A[]中的每一个元素都唯一对应于某一下标编号，记作A[0,n) = {A[0], A[1], .., A[n-1]}。其中，对于任何 0 ≤ i < j < n，A[i]都是A[j]的前驱(predecessor)，A[j]都是A[i]的后继(successor)。特别地，对于任何i ≥ 1，A[i-1]称作A[i]的直接前驱(immediate predecessor)；对于任何i ≤ n - 2，A[i+1]称作A[i]的直接后继(immediate successor)。任一元素的所有前驱构成其前缀(prefix)，所有后继构成其后缀(suffix)。
- 具体地，若数组A[]存放空间的起始位置为A，且每个元素占用s个单位的空间，则元素A[i]对应的物理地址为：A + i * s，因其中元素的物理地址与其下标之间满足这种线性关系，故亦称作线性数组(linear array)。
向量
- 以此前介绍的线性递归为例，运行过程中所出现过的所有递归实例，按照相互调用的关系可构成一个线性序列。在此序列中，各递归实例的秩反映了它们各自被创建的时间先后，每一递归实例的秩等于早于它出现的实例总数。反过来，通过r亦可唯一确定$e = v_r$。这是向量特有的元素访问方式，称作循秩访问(call-by-rank)。
- 向量的特点：不限定同一向量中的各元素都属于同一基本类型，它们本身可以是来自于更具一般性的某一类的对象。另外，各元素也不见得同时具有某一数值属性，故而并不保证它们之间能够相互比较大小。
构造与析构
向量结构在内部维护一个元素类型为T的私有数组_elem[]：其容量由私有变量_capacity指示；有效元素的数量(即向量当前的实际规模)，则有_size指示。此外还进一步地约定，在向量元素的秩、数组单元的逻辑编号以及物理地址之间，具有如下对应关系：
向量中秩为r的元素，对应于内部数组中的_elem[r]，其物理地址为_elem+r
默认构造方法
默认的构造方法是，首先根据创建者指定的初始容量，向系统申请空间，以创建内部私有数组_elem[]；若容量未明确指定，则使用默认值DEFAULT_CAPACITY。接下来，鉴于初生的向量尚不包含任何元素，故将指示规模的变量_size初始化为0。
整个过程顺序进行，没有任何迭代，故若忽略用于分配数组空间的时间，共需常数时间。
基于复制的构造方法
向量的另一典型创建方式，是以某个已有的向量或数组为蓝本，进行(局部或整体的)克隆。1
2
3
4
5
6
7
8vector_constructor_by_copying.h
template <typename T> // 元素类型
void Vector<T>::copyFrom(T const *A, Rank lo, Rank hi) { // 以数组区间A[lo,hi)为蓝本复制向量
_elem = new T[_capacity = 2 * (hi - lo) ]; _size = 0; // 分配空间，规模清零
while(lo < hi) // A[lo, hi)内的元素逐一
_elem[_size++] = A[lo++]; // 复制至_elem[0, hi-lo)
}
copyFrom()首先根据待复制区间的边界，换算出新向量的初始规模；再以双倍的容量，为内部数组_elem[]申请空间。最后通过一趟迭代，完成区间A[lo, hi) (注意这里是左闭右开) 内各元素的顺次复制。
若忽略开辟新空间所需的时间，运行时间应正比于区间宽度，即$O(hi - lo) = O(size)$。
需强调的是，由于向量内部含有动态分配的空间，默认的运算符”=”不足以支持向量之间的直接赋值(因为向量内存储数据的数据类型并非全是基本数据类型)。
为适应此类赋值操作的需求，重载向量的赋值运算符。1
2
3
4
5
6
7vector_assignment.h
template <typename T> Vector<T>& Vector<T>::operator=(Vector<T> const& V) { // 重载
if (_elem) delete [] _elem; // 释放原有内容
copyFrom(V.elem, 0, V.size()); // 整体复制
return *this; // 返回当前对象的引用，以便链式赋值
}
析构方法
与析构函数不同，同一对象只能有一个析构函数，不得重载。
向量对象的析构过程，只需释放用于存放元素的内部数组_elem[]，将其占用的空间交还操作系统。_capacity和_size之类的内部变量无需做任何处理，它们将作为向量对象自身的一部分被系统回收，此后既无需也无法被引用。
若不计系统用于空间回收的时间，整个析构过程只需O(1)时间。
动态空间管理
静态空间管理
- 内部数组所占物理空间的容量，若在向量的生命期内不允许调整，则称作静态空间管理策略。
- 向量实际规模与其内部数组容量的比值(即_size/_capacity)，亦称作装填因子(load factor)。
如何才能保证向量的装填因子既不致于超过1，也不致于太接近于0？
为此，需要改用动态空间管理策略。其中一种有效的方法，即使用所谓的可扩充向量。
可扩充向量
可扩充向量(extendable vector) 的原理：若内部数组仍有空余，则操作可照常执行。每经一次插入(删除)，可用空间都会减少(增加)一个单元。一旦空间耗尽，就动态地扩大内部数组的容量。这里的难点及关键在于：
如何实现扩容？新的容量取作多少才算适宜？
一种可行的方法，我们需要另行申请一个容量更大的数组B[]，并将原数组中的成员集体搬迁至新的空间，此后访客顺利地插入新元素e而不致溢出。当然，原数组所占的空间，需要及时释放并归还操作系统。
扩容
基于以上策略的扩容算法expand()。1
2
3
4
5
6
7
8
9
10vector_expand.h
template <typename T> void Vector<T>::expand() { // 向量空间不足时扩容
if(_size < _capacity) return; // 尚未满员时，不必扩容
if(_capacity < DEFAULT_CAPACITY) _capacity = DEFAULT_CAPACITY; // 不低于最小容量
T* oldElem = _elem; _elem = new T[_capacity <<= 1]; // 容量加倍
for(int i = 0; i < _size; i++)
_elem[i] = oldElem[i]; // 复制原向量内容(T为基本类型，或已重载赋值操作符'='）
delete [] oldElem; // 释放原空间
}
请注意，新数组的地址由操作系统分配，与原数据区没有直接的关系。这种情况下，若直接饮用数组，往往会导致共同指向原数组的其他指针失效，称为野指针 (wild pointer)；而封装为向量后，即可继续准确地引用各元素，从而有效地避免野指针的风险。
这里的关键在于，新数组的容量总是取作原数组的两倍————这正是上述后一问题的答案。取作二倍的目的是预留一些空间后，使得将来足够长的时间内，不会因为有必要扩容而打断我们的计算过程。下面介绍通过分摊分析对用于扩容的时间成本进行分析。
分摊分析(amortized analysis)
分摊复杂度
对可扩充向量的足够多次连续操作，并将其间所消耗的时间，分摊至所有的操作。如此分摊平均至单词操作的时间成本，称作分摊运行时间(amortized running time)。
注意这一指标与平均运行时间(average running time) 有着本质的区别。后者是按照某种假定的概率分布，对各种情况下所需执行时间的加权平均，故亦称作期望运行时间(expected running time)。而前者则要求，参与分摊的操作必须构成和来自一个真实可行的操作序列，而且该序列还必须足够地长。
相对而言，分摊复杂度可以针对计算成本和效率，做出更为客观而准确的设计(优点)。比如在这里，在任何一个可扩充向量的生命期内，在任何足够长的连续操作序列中，以任何固定间隔连续出现上述最坏情况的概率均为0，故常规的平均复杂度根本不具任何参考意义。
O(1)分摊时间
假定数组的初始容量为某一常数N。既然是估计复杂度的上界，故不妨设向量的初始规模也为N——即将溢出。另外不难看出，除插入操作外，向量其余的接口操作既不会直接导致溢出，也不会增加伺候溢出的可能性，因此不妨考察最坏的情况，假设在伺候需要连续地进行n次insert()操作，n >> N。首先定义如下函数：
size(n) = 连续插入n个元素后向量的规模
capacity(n) = 连续插入n个元素后数组的容量
T(n) = 为连续插入n个元素而花费于扩容的时间
其中，向量规模从N开始随着操作的进程逐步递增，故有：$size(n) = N + n$
既然不致溢出，故装填因子绝不会超出100%。同时，这里的扩容采用了“懒惰”策略——只有在的确即将发生溢出时，才不得不将容量加倍——因此装填因子也始终不低于50%。
概括起来，始终应有：
$size(n) ≤ capacity(n) ≤ 2 * size(n)$
考虑到N为常数，故有：
$capacity(n) = Θ(size(n)) = Θ(n)$
容量以2为比例按指数速度增长，在容量达到capacity(n)之前，共做过$Θ(log_2n)$次扩容，每次扩容所需时间线性正比于当时的容量(或规模)，且同样以2为比例按指数速度增长。因此，消耗于扩容的时间累计不过：
$T(n) = 2N + 4N + 8N + … + capacity(n) < 2 * capacity(n) = Θ(n)$
将其分摊到其间的连续n次操作，单次操作所需的分摊运行时间应为$O(1)$。
其它扩容策略
早期可扩充向量多采用另一策略：一旦有必要，则追加固定数目的单元。实际上，无论采用的固定常数多大，在最坏情况下，此类数组单次操作的分摊时间复杂度都高达$Ω(n)$。
缩容
1 | vector_shrink.h |
与expand()操作类似，尽管单次shrink()操作需要线性量级$Ω(n)$的时间，但其分摊复杂度亦为$O(1)$。
常规向量
直接引用元素
重载操作符”[]”，使向量ADT访问元素的方式与数组直接通过下标访问元素的方式(形如”A[i]”)相同。1
2
3
4
5vector_bracket.h
代码2.6 重载向量操作符[]
template <typename T> T& Vector<T>::operator[](Rank r) const // 重载下标操作符
{ return _elem[r];} // assert: 0 <= r < _size
置乱器
置乱算法
1 | permute.h |
该算法从置乱区间的末元素开始，逆序地向前逐一处理各元素。对每一个当前元素V[i - 1]，先通过调用rand()函数在[0, i)之间等概率地随机选取一个元素，再令二者互换位置。注意，这里的交换操作swap()，隐含了三次基于重载操作符”[]”的赋值。
每经过一步这样的迭代，置乱区间都会向前拓展一个单元。因此经过O(n)步迭代后，即实现了整个向量的置乱。
从理论上讲，使用这里的permute()算法，不仅可以枚举出同一向量所有可能的排列，而且能够保证生成各种排列的概率相等。
区间置乱接口
1 | vector_unsort.h |
通过该接口，可以均匀地置乱任一向量区间[lo, hi)内的元素，故通用性有所提高。可见，只要将该区间等效地视作另一向量V，即可从形式上完整地套用以上permute()算法的流程。
尽管如此，还要特别留意代码2.7和代码2.8之间的细微差异：后者是通过下标，直接访问内部数组的元素；而前者则是借助重载的操作符”[]”，通过秩间接地访问向量的元素。
判等器与比较器
从算法的角度来看，”判断两个对象是否相等”与”判断两个对象的相对大小”都是至关重要的操作，它们直接控制者算法执行的分支方向。这两种操作之间既有联系也有区别，不能相互替代。比如，有些对象只能比对但不能比较；反之，支持比较的对象未必支持比对。不过，出于简化的考虑，在很多场合并不需要严格地将二者区分开来。
算法实现的简洁性和通用性，在很大程度上体现于：针对整数等特定数据类型的某种实现，可否推广至可比较或可比对的任何数据类型，而不必关心如何定义以及判定其大小或相等关系。若能如此，就可以将比对和比较操作的具体实现剥离出来，直接讨论算法流程本身。
为此，通常可以采用两种方法。其一，将比对操作和比较操作分别分装成通用的判等器和比较器。其二，在定义对应的数据类型时，通过重载”<”和”==”之类的操作符，给出大小和相等关系的具体定义及其判别方法。
在一些复杂的数据结构中，内部元素本身的类型可能就是指向其它对象的指针；而从外部更多关注的，则往往是其所指对象的大小。若不加处理而直接根据指针的数值(即被指对象的物理地址)进行比较，则所得结果将毫无意义。
无序查找
判等器
仅支持比对，但未必支持比较的向量，称作无序向量(unsorted vector)。
顺序查找
逐个比对的查找方式，称作顺序查找(sequential search)。
实现
1 | vector_find.h |
其中若干细微之处，需要体会。比如，当同时多个命中元素时，本书统一约定返回其中秩最大者——故这里采用了自后向前的查找次序。如此，一旦命中即可立即返回，从而省略掉不必要的比对。另外，查找失败时约定统一返回-1。这不仅简化了对查找失败情况的判别，同时也使此时的返回结果更加易于理解——只要假想者在秩为-1处植入一个与任何对象对相等的哨兵元素，则返回该元素的秩当且仅当查找失败。
最后一处需要留意。while循环的控制逻辑由两部分组成，首先判断是否已抵达通配符，再判断当前元素与目标元素是否相等。利用了C/C++语言中逻辑表达式的短路求值特性，在前一判断非真厚循环会立即终止，而不致因试图引用已越界的秩(-1)而出错。
复杂度
最坏情况，查找终止于首元素_elem[lo]，运行时间为O(hi - lo) = O(n)。最好情况下，查找命中于末元素_elem[hi - 1]，仅需O(1)时间。对于规模相同、内部组成不同的输入，渐进运行时间却有本质区别，故此类算法也称作输入敏感的(input sensitive) 算法。
插入
实现
1 | vector_insert.h |
插入前首先调用expand()算法核对是否即将溢出，若有必要，则加倍扩容。为保证数组元素的物理地址连续，随后需要将后缀_elem[r, _size)（若非空)整体后移一个单元。这些后继元素自后向前的搬迁次序不能颠倒，否则会因元素被覆盖而造成数据丢失(自后向前的原因)。在单元_elem[r]腾出之后，方可将待插入对象e置入其中。
复杂度
时间主要消耗于后继元素的后移，线性正比于后缀的长度，故总体为$O( size - r + 1)$。
新插入元素越靠后(前)所需时间越短(长)。特别地，r取最大值_size时为最好情况，只需$O(1)$时间；r取最小值0时，需要$O(size)$时间。一般地，若插入位置等概率分布，则平均运行时间为$O(size) = O(n)$，线性正比于向量的实际规模。
删除
删除操作重载有两个接口，remove(lo, hi)用以删除区间[lo, hi)内的元素，而remove(r)用以删除秩为r的单个元素。乍看起来，利用后者即可实现前者：令r从hi - 1到lo递减，反复调用remove(r)。实际可行的思路恰好相反，应将单元素删除视作区间删除的特例，并基于后者实现前者(单元素删除与区间删除的关系)。如此可将移动操作的总次数控制在$O(m)$以内，而与待删除区间的宽度无关。
区间删除：remove(lo, hi)
1 | vector_removeInterval.h |
设[lo, hi)为向量的合法区间，则其后缀[hi, n)需整体前移hi - lo个单元。与插入算法同理，这里后继元素自前往后的移动次序也不能颠倒。
单元素删除：remove(r)
1 | vector_remove.h |
复杂度
remove(lo, hi)的计算成本，主要消耗于后续元素的前移，线性正比于后缀的长度，总体不过$O(m+1) = O(size - hi + 1)$。区间删除操作所需的时间，应该仅取决于后继元素的数目，而与被删除区间本社你的宽度无关。特别地，基于该接口实现的单元素删除接口remove(r)需耗时$O(size - r)$。也就是说，被删除元素在向量中的位置越靠后(前)所需时间越短(长)，最好为$O(1)$，最坏为$O(n) = O(size)$。
唯一化
实现
1 | vector_deduplicate.h |
该算法自前往后逐一考察各元素_elem[i]，并通过调用find()接口，在其前缀中寻找与之雷同者。若找到，则随即删除；否则，转而考察当前元素的后继。
正确性
算法的正确性由以下不变性保证:
在while循环中，在当前元素的前缀_elem[0, i)内，所有元素彼此互异。
初次进入循环时i=1，只有唯一的前驱_elem[0]，故不变性自然满足。
假设在转至元素e = _elem[i]之前不变性一直成立。于是，经过针对该元素的一步迭代之后，无非两种结果：
1)若元素e的前缀_elem[0, i)中不含与之雷同的元素，则在做过i++之后，新的前缀_elem[0, i)将继续满足不变性，而且其规模增加一个单位。
2)反之，若含存在与e雷同的元素，则由此前一直满足的不变性可知，这样的雷同元素不超过一个。因此在删除e之后，前缀_elem[0, i)依旧保持不变性。
复杂度
这里所需的时间，主要消耗于find()和remove()两个接口，前一部分时间应先行正比于查找区间的宽度，即前驱的总数；后一部分时间应线性正比于后继的总数。因此，每步迭代所需时间为$O(n)$，总体复杂度应为$O(n^2)$。
遍历
实现
1 | vector_traverse.h |
traverse()遍历的过程，就是自前向后逐一对各元素实施同一基本操作。而具体采用何种操作，可通过两种方式指定。前一种方式借助函数指针*visit()指定某一函数，该函数只有一个参数，其类型为对向量元素的引用，故通过该函数即可直接访问或修改向量元素。另外，也可以函数对象的形式，指定具体的遍历操作。这类对象的操作符”()”经重载之后，在形式上等效于一个函数接口，故此得名。
相比较而言，后一形式的功能更强，适用范围更广。比如，函数对象的形式支持对向量元素的关联修改。也就是说，对各元素的修改不仅可以相互独立地进行，也可以根据某个(些)元素的数值相应地修改另一元素。前一形式也可实现这类功能，但要繁琐很多。
复杂度
遍历操作本身只包含一层线性的循环迭代，故除了向量规模的因素外，遍历所需时间应线性正比于所统一指定的基本操作所需的时间。
有序向量
若向量S[0, n)中的所有元素不仅按线性次序存放，而且其数值大小也按此次序单调分布，则称作有序向量(sorted vector)。有序向量不要求元素互异，故通常约定其中的元素自前(左)向后(右)构成一个非降序列，即对任意$0 ≤ i < j < n$都有$S[i] ≤ S[j]$。
有序性甄别
1 | vector_disordered.h |
顺序扫描整个向量，逐一比较每一对相邻元素——向量已经有序，当且仅当它们都是顺序的。
唯一化
低效版
实现
1 | vector_uniquify_slow.h |
正确性
其正确性基于如下事实：有序向量中的重复元素必然前后紧邻。于是，可以自前向后地逐一检查各对相邻元素:若二者雷同则调用remove()接口删除靠后者，否则转向下一对相邻元素。如此，扫描结束后向量中将不再含有重复元素。
复杂度
运行时间主要消耗于while循环，共需迭代_size - 1 = n - 1步。此外，在最坏情况下，每次循环都需要执行一次remove()操作，由前面可知remove()操作的复杂度线性正比于被删除元素的后继元素总数。因此，当大量甚至所有元素均雷同时，用于所有这些remove()操作的时间总量将高达：
$(n - 2) + (n - 3) + … + 2 + 1 = O(n^2)$
与向量未排序时相同，说明该方法未能充分利用此时向量的有序性。
改进思路
低效版唯一化过程复杂度过高的根源是，在对remove()接口的各次调用中，同一元素可能作为后继元素向前移动多次，且每次仅移动一个单元。
因为此时的每组重复元素都必然前后紧邻地集中分布，所以可以区间为单位成批地删除前后紧邻的各组重复元素，并将其后继元素(若存在)统一地大跨度前移。具体地，若V[lo, hi)为一组相邻的重复元素，则所有的后继元素V[hi, _size)可统一地整体前移hi - lo - 1个单元。
高效版
1 | vector_uniquify.h |
既然各组重复元素必然彼此相邻地构成一个子区间，故只需依次保留各区间的起始元素。于是，这里引入了变量i和j。每经过若干次移动，i和j都将分别指向下一对相邻子区间的首元素；在将后者转移至前者的后继位置之后(相比低效版这里是元素的复制而不是前移，因此不需要remove()操作)，即可重复上述过程。
复杂度
while循环的每一次迭代，仅需对元素数值做一次比较，向后移动一到两个位置指针，并至多向前复制一个元素，故只需常数时间。而在整个算法过程中，每经过一次迭代秩j都必须加1，鉴于j不能超过向量的规模n，故共需迭代n次。由此可知，uniquify()算法的时间复杂度应为$O(n)$，较之uniquify_slow()的$O(n^2)$,整整提高了一个线性因子。
反过来，在遍历所有元素之前不可能确定是否有重复元素，故就渐进复杂度而言，能在$O(n)$时间内完成向量的唯一化已属最优。能做到这一点的关键在于向量已经排序。
查找
二分查找(版本A)
实现
1 | vector_search_binary_a.h |
为在有序向量区间[lo, hi)内查找元素e，该算法以中点$mi = (lo + hi)/2$为界，将其大致平均地分为前、后两个子向量。随后通过一至两次比较操作，确定问题转化的方向。通过快捷的整数移位操作回避了相对更加耗时的除法运算。另外，通过引入lo、hi和mi等变量，将减治算法通常的递归模式改成了迭代模式。
复杂度
以上算法采取的策略可概括为，以”当前区间内居中的元素”作为目标元素的试探对象。从应对最坏情况的保守角度来看，这一策略是最优的——每一步迭代之后无论沿着哪个方向深入，新问题的规模都将缩小一半。因此，这一策略也称作二分查找(binary search)。
随着迭代的不断深入，有效的查找区间宽度将按1/2的比例以几何级数的速度递减。于是，经过至多$log_2(hi -lo)$步迭代后，算法必然终止。鉴于每步迭代仅需常数时间，故总体时间复杂度不超过:$O(log_2(hi - lo)) = O(logn)$。
与之前的顺序查找算法$O(n)$复杂度相比，$O(logn)$几乎改进了一个线性因子。
查找长度
以上迭代过程所涉及的计算，主要分为两类：元素的大小比较、秩的算术运算及其赋值。虽然二者均属于$O(1)$复杂度的基本操作，但元素的秩无非是(无符号)的整数，而向量元素的类型则通常更为复杂，甚至复杂到未必能够保证在常数时间内完成(习题【2-17】)。因此就时间复杂度的常系数而言，前一类计算的权重远远高于后者，而查找算法的整体效率也更主要地取决于所执行的元素大小比较操作的次数，即所谓查找长度(search length)。
成功查找长度
对于长度为n的有序向量，共有n种可能的成功查找，分别对应于某一元素。实际上，每一种成功查找所对应的查找长度，仅取决于n以及目标元素所对应的秩，而与元素的具体数值无关。
为了估计出一半情况下的成功查找长度，不失一般性地，仍在等概率条件下考察长度为$n = 2^k - 1$的有序向量，并将其对应的平均成功查找长度记作$C_{average}(k)$，将所有元素对应的查找长度总和记作$C(k) = C_{average}(k) \cdot (2^k - 1)$。
特别地，当k = 1时向量长度n = 1，成功查找仅有一种情况，故有边界条件:
$C_{average}(1) = C(1) = 2$
以下采用递推分析法。对于长度为$n = 2^k - 1$的有序向量，每步迭代都有三种可能的分支:经过1次成功的比较后，转化为一个规模为$2^{k-1}-1$的新问题；经2次失败的比较后，终止于向量中的某一元素，并确认在此处成功命中；经1次失败的比较另加1次成功的比较后，转化为另一个规模为$2^{k-1} -1$的新问题。
根据以上递推分析的结论，可得递推式如下:
$$
\begin{aligned}
C(k)& = [C(k-1) + (2^{k-1} -1 )] + 2 + [C(k-1) + 2 \times (2^{k-1} -1 )] \\
& = 2 \cdot C(k-1) + 3 \cdot 2^{k-1} - 1
\end{aligned}
$$
若令：
$F(k) = C(k) - 3k \cdot 2^{k-1} - 1$
则有:
$F(1) = -2$
$$
\begin{aligned}
F(k) & = 2 \cdot F(k - 1) = 2^2 \cdot F(k - 2) = 2^3 \cdot F(k - 3) = … \\
& = 2^{k-1} \cdot F(1) = -2^k
\end{aligned}
$$
于是：
$$
\begin{aligned}
C(k) & = F(k) + 3k \times 2^{k-1} + 1 \\
& = -2^k + 3k \times 2^{k-1} + 1 \\
& = (3k/2 -1) \cdot (2^k - 1) + 3k/2
\end{aligned}
$$
进而：
$$
\begin{aligned}
C_{average}(k) & = C(k) / (2^k - 1) \\
& = 3k/2 - 1 + 3k/2/(2^k - 1) \\
& = 3k/2 - 1 + O(\varepsilon) \\
\end{aligned}
$$
也就是说，若忽略末尾趋于收敛的波动项，平均查找长度应为：
$O(1.5k) = O(1.5 \cdot log_2n)$
失败查找长度
按照上述代码，失败查找的终止条件必然是”lo ≥ hi”，也就是说，只有在有效区间宽度缩减至0时，查找方以失败告终。因此，失败查找的时间复杂度应为确定的$Θ(logn)$。
仿照以上对平均成功查找长度的递推分析方法，不难证明(习题【2-20】)，一般情况下的平均失败查找长度亦为$O(1.5 \cdot log_2n)$。
不足
尽管二分查找算法(版本A)即便在最坏情况下也可保证$O(logn)$的渐进时间复杂度，但就其常系数1.5而言仍有改进余地。下面介绍Fibonacci查找将完成这改进。
Fibonacci查找
递推方程
递推方程法既是复杂度分析的重要方法，也是优化算法时确定突破口的有力武器。
最终求解所得到的平均复杂度，主要取决于$(2_{k-1} - 1)$和$2 \times (2_{k-1} - 1)$两项，其中的$(2_{k-1} - 1)$为子向量的宽度，而系数1和2则是算法为深入前、后子向量，所需做的比较操作次数。以此前的二分查找算法版本A为例，之所以存在均衡性方面的缺陷，根源来自于这两项的大小不相匹配。
基于这一理解，发现解决问题的思路不外乎两种：
其一，调整前、后区域的宽度，适当地加长(缩短)前(后)子向量；
其二，统一沿两个方向深入所需要执行的比较次数，比如都统一为一次；
黄金分割
简化起见，设向量长度n = fib(k) - 1
fibsearch(e, 0, n)查找可以mi = fib(k - 1) - 1作为前、后子向量的切分点。如此，前、后子向量的长度将分别是：
$fib(k-1) - 1$
$fib(k-2) - 1 = (fib(k) - 1) - (fib(k - 1) - 1) - 1$
于是，无论朝哪个方向深入，新向量的长度从形式上都依然是某个Fibonacci数减一，故这一处理手法可以反复套用，直至因在S[mi]处命中或向量长度收缩至零而终止。这种查找算法，亦称作Fibonacci查找(Fibonaccian search)。
实现
1 | vector_search_fibonaccin.h |
算法主体框架与二分查找大致相同，主要区别在于以黄金分割点取代中点作为切分点。为此，需要借助Fib对象(习题【1-22】)，实现对Fibonacci数的高效设置与获取。
尽管以下的分析多以长度为fib(k) - 1的向量为例，但这一实现完全可适用于长度任意的向量中的任意子向量。为此，只需在进入循环之前调用构造器Fib(n = hi - lo)，将初始长度设置为”不小于n的最小Fibonacci项”。这一步所需花费的$O(log_{\phi}n)$时间，分摊到后续的$O(log_{\phi}n)$步迭代中，并不影响算法整体的渐进复杂度。
定量分析
Fibonacci查找算法最好、最坏情况的成功查找长度与二分算法的结论完全一致。
依然将长度为n = fib(k) - 1的有序向量的平均成功查找长度记作$C_{average}(k)$，将所有元素对应的查找长度总和记作$C(k) = C_{average}(k) \cdot (fib(k) - 1)$。
同理，可得边界条件及递推式如下:
$C_{average}(2) = C(2) = 0$
$C_{average}(3) = C(3) = 2$
$$
\begin{aligned}
C(k) & = [C(k-1) + (fib(k-1) - 1)] + 2 + [C(k-2) + 2 \times (fib(k-2) - 1)] \\
& = C(k - 2) + C(k - 1) + fib(k - 2) + fib(k) - 1
\end{aligned}
$$
结合以上边界条件，可以解得:
(令$F(k) = -C(k) + k \cdot fib(k) + 1$，则有$F(0) = 1$，$F(1) = 2$，$F(k) = F(k-1) + F(k-2)$)
$$
\begin{aligned}
C(k) & = k \cdot fib(k) - fib(k + 2) + 1 \\
& = (k - \phi^2) \cdot fib(k) + 1 + O(\mathcal{E})
\end{aligned}
$$
其中，$\phi = (\sqrt{5} + 1) / 2 = 1.618$
于是
$$
\begin{aligned}
C(k) & = C(k) / (fib(k) - 1)\\
& = k - \phi^2 + 1 + (k - \phi^2) / (fib(k) - 1) + O(\mathcal{E}) \\
& = k - \phi^2 + 1 + O(\mathcal{E}) \\
\end{aligned}
$$
忽略末尾趋于收敛的波动项，平均查找长度的增长趋势为:
$O(k) = O(log_{\phi}n) = O(log_{\phi}2 \cdot log_2n) = O(1.44 \cdot log_2n)$
较之之前二分查找算法(版本A)的$O(1.5 \cdot log2n)$，效率略有提高。
二分查找(版本B)
从三分支对应两分支
为了解决二分查找算法版本A的不均衡性，Fibonacci查找算法已通过采用黄金分割点，在一定程度上降低了时间复杂度的常系数。
还有另一更为直接的方法，即令以上两项的常系数同时等于1。也就是说，无论朝哪个方向深入，都只需做1次元素的大小比较。相应地，算法在每步迭代中(或递归层次上)都只有两个分支方向，而不再是三个。
具体过程与二分查找算法的版本A基本类似。不同之处是，在每个切分点A[mi]处，仅做一次元素比较。具体地，若目标元素小于A[mi]，则深入前端子向量A[lo, mi]继续查找；否则，深入后端子向量A[mi, hi)继续查找。
实现
1 | vector_search_binary_b.h |
注意与二分查找版本A的差异。首先，每一步迭代只需判断是否e < A[mi]，即可相应地更新有效查找区间的右边界(hi = mi)或左边界(lo = mi)。另外，只有等到区间的宽度已不足2个单元时迭代才会终止，最后再通过一次比对判断查找是否成功。
性能
尽管版本B中的后端子向量需要加入A[mi]，但得益于mi总是位于中央位置，整个算法$O(logn)$的渐进复杂度不受任何影响。
版本B中只有在向量有效区间宽度缩短至1个单元时算法才会终止，而不能像版本A一旦命中就能及时返回。因此，最好情况下的效率有所倒退。作为补偿，最坏情况下的效率相应地有所提高。实际上无论是成功查找或失败查找，版本B各分支的查找长度更加接近，故整体性能更趋稳定。
二分查找(版本C)
实现
1 | vector_search_binary_c.h |
该版本的主体结构与版本B一致，故不难理解，二者的时间复杂度相同。
正确性
版本C与版本B的差异，主要有三点。首先，只有当有效区间的宽度缩短至0(而不是1)时，查找方告终止。另外，在每次转入后端分支时，子向量的左边界取作mi + 1而不是mi。
通过数学归纳可以证明，版本C中的循环体，具有如下不变性:
A[0, lo)中的元素皆不大于e；A[hi, n)中的元素皆大于e
首先迭代时，lo = 0且hi = n，A[hi, n)均空，不变性自然成立。
设在某次进入循环时以上不变性成立，以下无非两种情况。若e < A[mi]，在令hi = mi并使A[hi, n)向左扩展之后，该区间内的元素皆不小于A[mi]，也仍然大于e。反之，若A[mi] ≤ e，在令lo = mi + 1并使A[0, lo)向右拓展之后，该区间内的元素皆不大于A[mi]，也仍然不大于e。上述不变性得以延续。
循环终止时，lo = hi。考察此时的元素A[lo - 1]和A[lo]:作为A[lo, n) = A[hi, n)内的第一个元素，A[lo]必大于e。也就是说A[lo - 1]即是原向量中不大于e的最后一个元素。因此在循环结束后，无论成功与否，只需返回lo - 1即可——这也是版本C与版本B的第三点差异。
排序与下界
有序性
有序性在很多场合都能极大地提高计算的效率。
排序及其分类
在解决许多应用问题时一种普遍采用的策略是，首先将向量转换为有序向量，再调用有序向量支持的各种高效算法。
排序算法分类
排序算法有多种，可从多个角度对其进行分类。
- 根据其处理数据的规模与存储的特点不同，可分为：
- 内部排序算法
- 外部排序算法
前者处理的数据规模相对不大，内存足以容纳；后者处理的数据规模很大，必须借助外部甚至分布式存储器，在排序计算过程的任一时刻，内存中只能容纳其中一小部分数据。
- 根据输入形式的不同，可分为：
- 离线算法(offline algorithm)
- 在线算法(online algorithm)
前一情况下，待排序的数据以批处理的形式整体给出；而在网络计算之类的环境中，待排序的数据通常需要实时生成，在排序算法启动后数据才陆续到达。
- 针对所依赖的体系结构不同，又可分为：
- 串行排序算法
- 并行排序算法
- 根据排序算法是否采用随机策略，可分为：
- 确定式
- 随机式
本书讨论的范围，主要集中于确定式串行脱机的内部排序算法。
下界
一般地，任一问题在最坏情况下的最低计算成本，即为该问题的复杂度下界(lower bound)。一旦某一算法的性能达到这一下界，即意味着它已是最坏情况下最优的(worst-case optimal)。
以下结合比较树模型，介绍界定问题复杂度下界的一种重要方法。
比较树
基于比较的分支
用节点(圆圈)表示算法过程中的不同状态，用有向边表示不同状态之间的相互转换，就可以将算法转化为树形结构。
这一转化方法也可以推广并应用于其他算法。一般地树根结点对应算法入口处的起始状态；内部节点对应过程中的某步计算，通常属于基本操作；叶节点则对应经一系列计算后某次运行的终止状态。如此借助这一树形结构，可以涵盖对应算法所有可能的执行流程。
比较树
算法所有可能的执行过程，都可涵盖于这一树形结构中。具体地，该树具有以下性质：
- 每一内部节点各对应于一次比对(称量)操作；
- 内部节点的左、右分支，分别对应于在两种比对结果(是否等重)下的执行方向；
- 叶节点(或等效地，根到叶节点的路径)对应于算法某次执行的完整过程及输出；
- 反过来，算法的每一运行过程都对应于从根到某一叶节点的路径。
按上述规则与算法相对应的树，称作比较树(comparison tree)。
无论什么算法，只要其中的分支完全取决于不同变量或常量的比对或比较结果，则该算法所有可能的执行过程都可表示和概括为一棵比较树。反之，凡可如此描述的算法，都可称作基于比较式算法(comparison-based algorithm)，简称CBA式算法。
CBA式算法在最坏情况下的最低执行成本，可由对应的比较树界定。
估计下界
最小树高
考察任一CBA式算法，设CT(A)为与之对应的一棵比较树。
根据比较树的性质，算法A每一次运行所需的时间，将取决于对应叶节点到根节点的距离(称作叶节点的深度)；而算法A在最坏情况下的运行时间，将取决于比较树中所有叶节点的最大深度(称作该树的高度，记作$h(CT(A))$)。因此就渐进的意义而言，算法A的时间复杂度应不低于$\Omega(h(CT(A)))$。
如何估计这些比较树的最小高度？
为此，只需考察书中所含叶节点(可能的输出结果)的数目。具体地，在一棵高度为h的二叉树中，叶节点的数目不可能多余$2^h$。因此反过来，若某一问题的输出结果不少于N种，则比较树中叶节点也不可能少于N个，树高h不可能低于$log_2N$(习题【7-3】)
排序
任一CBA式排序算法所对应比较树的高度应为:
$h ≥ \lceil log_3(n!) \rceil = \lceil log_3e \cdot ln(n!) \rceil = \Omega(nlogn)$
因此最坏情况下CBA排序算法至少需要$\Omega(nlogn)$时间，其中n为待排序元素数目。
需要强调的是，这一$\Omega(nlogn)$下界是针对比较树模型而言的。事实上还有很多不属此类的排序算法，并且其中一些算法在最坏情况下的运行时间，有可能低于这一下界，但与上述结论并不矛盾。
排序器
起泡排序
起泡排序
1 | vector_bubblesort.h |
反复调用单趟扫描交换算法，直至逆序现象完全消除。
扫描交换
1 | vector_bubble.h |
依次比对各对相邻元素，每当发现逆序即令二者彼此交换；一旦经过某趟扫描后未发现任何逆序的相邻元素，即意味着排序任务已经完成，则通过返回标志”sorted”，以便主算法及时终止。
重复元素与稳定性
稳定性(stability)是对排序算法更为细致的要求，重在考察算法对重复元素的处理效果。具体地，在将向量A转换为有序向量S之后，设$A[i]$对应于$S[k_i]$。若对于A中每一对重复元素$A[i] = A[j]$(相应地$S[k_i] = S[k_j]$)，都有i < j当且仅当$k_i < k_j$，则称该排序算法是稳定算法(stable algorithm)。简而言之，稳定算法的特征是，重复元素之间的相对次序在排序前后保持一致。反之，不具有这一特征的排序算法都是不稳定算法(unstable algorithm)。
归并排序
有序向量的两路归并
二路归并，就是将两个有序序列合并成一个有序序列。归并排序所需的时间，也主要决定于各趟二路归并所需时间的总和。
二路归并属于迭代式算法。每步迭代中，只需比较两个待归并向量的首元素，将小者取出并追加到输出向量的末尾，该元素在原向量中的后继则成为新的首元素。如此往复，直到，某一向量为空。最后，将另一非空的向量整体接至输出向量的末尾。
分治策略
1 | vector_mergesort.h |
均匀地将向量S[lo, hi)划分成两个子向量。借助以上的二路归并算法，通过递归调用将二者分别转换为有序向量，得到与原向量S对应的整个有序向量。
这里递归终止条件是当前向量长度：$n = hi -lo = 1$
仅含单个元素的向量必然有序，这一处理分支自然也就可以作为递归基。
二路归并接口的实现
1 | vector_merge.h |
约定参与归并的子向量在原向量中总是前、后相邻的，故借助三个入口参数即可界定其范围[lo, mi)和[mi, hi)。另外，为保证归并向量所得的子向量能够原地保存以便继续参与更高层的归并，这里使用了临时数组B[]存放前一向量[lo, mi)的副本(习题【2-28】)。
归并时间
二路归并算法merge()的渐进时间成本，取决于其中循环迭代的总次数。
每经过一次迭代，B[i]和C[k]之间的小者都会被移出并接至A的末尾(习题【2-29】和习题【2-30】)。这意味，每经过一次迭代，总和s = j + k都会加一。
考察这一总和s在迭代过程中的变化。初始时，有s = 0 + 0 = 0;而在迭代期间，始终有:
$s < lb + lc = (mi - lo) + (hi - mi) = hi - lo$
因此，迭代次数及所需时间均不超过$O(hi - mi) = O(n)$。
反之，按照算法的流程控制逻辑，无论子向量的内部元素组成及其相对大小如何，只有待到s = hi - lo时迭代方能终止。因此，该算法在最好情况下仍需$\Omega(n)$时间，概括而言应为$\Theta(n)$。
推广
二路归并只需线性时间的结论，并不限于相邻且等长的子向量。实际上，即便子向量在物理地址空间上并非前后衔接，且长度相差悬殊，该算法也依然可行且仅需线性时间。
更重要地，这一算法框架也可应用于列表——而且同样可以达到线性的时间效率。
排序时间
归并排序算法的时间复杂度采用递推方程分析法，为此首先将归并排序算法处理长度为n的向量所需时间记作$T(n)$。根据算法构思与流程，为对长度为n的向量归并排序，需递归地对长度各为n/2的两个子向量做归并排序，再花费线性时间做一次二路归并。如此，可得到如下递推关系：
$T(n) = 2 \times T(n/2) + O(n)$
另外，当子向量长度缩短到1时，递归即可终止并直接返回该向量。故有边界条件
$T(1) = O(1)$
联立以上递推式，可以解得(习题【2-26】)
$T(n) = O(nlogn)$
也就是说，归并算法可在$O(nlogn)$时间内对长度为n的向量完成排序。因二路归并算法的效率稳定在$\Theta(n)$，故更准确地讲，归并排序算法的时间复杂度应为$\Theta(nlogn)$。